翻訳と辞書 Words near each other ・ Combined Services (Pakistan) cricket team ・ Combined Services cricket team ・ Combined Services Detailed Interrogation Centre ・ Combined Services Entertainment ・ Combined Services Polo Club ・ Combinatorial game theory ・ Combinatorial group theory ・ Combinatorial hierarchy ・ Combinatorial map ・ Combinatorial meta-analysis ・ Combinatorial method ・ Combinatorial method (linguistics) ・ Combinatorial number system ・ Combinatorial optimization ・ Combinatorial principles ・ Combinatorial proof ・ Combinatorial search ・ Combinatorial species ・ Combinatorial topology ・ Combinatoriality ・ Combinatorica ・ Combinatorics ・ Combinatorics and dynamical systems ・ Combinatorics and physics ・ Combinatorics on words ・ Combinatorics, Probability and Computing ・ Combinatory categorial grammar ・ Combinatory logic ・ COMBINE ・ Combine Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Combinatorial proof ： ウィキペディア英語版 Combinatorial proof In mathematics, the term ''combinatorial proof'' is often used to mean either of two types of mathematical proof: * A proof by double counting. A combinatorial identity is proven by counting the number of elements of some carefully chosen set in two different ways to obtain the different expressions in the identity. Since those expressions count the same objects, they must be equal to each other and thus the identity is established. * A bijective proof. Two sets are shown to have the same number of members by exhibiting a bijection, i.e. a one-to-one correspondence, between them. The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof in combinatorics. However, as writes in his review of (a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory. ==Example== An archetypal double counting proof is for the well known formula for the number $\backslash tbinom\; nk$ of ''k''-combinations (i.e., subsets of size ''k'') of an ''n''-element set: :$\backslash binom\; nk=\backslash frac.$ Here a direct bijective proof is not possible: because the right-hand side of the identity is a fraction, there is no set ''obviously'' counted by it (it even takes some thought to see that the denominator always evenly divides the numerator). However its numerator counts the Cartesian product of ''k'' finite sets of sizes ''n'', , ..., , while its denominator counts the permutations of a ''k''-element set (the set most obviously counted by the denominator would be another Cartesian product ''k'' finite sets; if desired one could map permutations to that set by an explicit bijection). Now take ''S'' to be the set of sequences of ''k'' elements selected from our ''n''-element set without repetition. On one hand, there is an easy bijection of ''S'' with the Cartesian product corresponding to the numerator $n(n-1)\backslash cdots(n-k+1)$, and on the other hand there is a bijection from the set ''C'' of pairs of a ''k''-combination and a permutation ''σ'' of ''k'' to ''S'', by taking the elements of ''C'' in increasing order, and then permuting this sequence by ''σ'' to obtain an element of ''S''. The two ways of counting give the equation :$n(n-1)\backslash cdots(n-k+1)=\backslash binom\; nk\; k!,$ and after division by ''k''! this leads to the stated formula for $\backslash tbinom\; nk$. In general, if the counting formula involves a division, a similar double counting argument (if it exists) gives the most straightforward combinatorial proof of the identity, but double counting arguments are not limited to situations where the formula is of this form. == The benefit of a combinatorial proof == gives an example of a combinatorial enumeration problem (counting the number of sequences of ''k'' subsets ''S''1, ''S''2, ... ''S''''k'', that can be formed from a set of ''n'' items such that the subsets have an empty common intersection) with two different proofs for its solution. The first proof, which is not combinatorial, uses mathematical induction and generating functions to find that the number of sequences of this type is (2''k'' −1)''n''. The second proof is based on the observation that there are 2''k'' −1 proper subsets of the set , and (2''k'' −1)''n'' functions from the set to the family of proper subsets of . The sequences to be counted can be placed in one-to-one correspondence with these functions, where the function formed from a given sequence of subsets maps each element ''i'' to the set . Stanley writes, “Not only is the above combinatorial proof much shorter than our previous proof, but also it makes the reason for the simple answer completely transparent. It is often the case, as occurred here, that the first proof to come to mind turns out to be laborious and inelegant, but that the final answer suggests a simple combinatorial proof.” Due both to their frequent greater elegance than non-combinatorial proofs and the greater insight they provide into the structures they describe, Stanley formulates a general principle that combinatorial proofs are to be preferred over other proofs, and lists as exercises many problems of finding combinatorial proofs for mathematical facts known to be true through other means. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Combinatorial proof」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.